package sort;

/**
 * @Author: Ma JiBin
 * @Email: 1423553596@qq.com
 * @Date: 2018/10/25 17:09
 * @Description: 快速排序算法
 * 算法思想：在数组中任选一个K值，将数组中所有大于K值得数值都转移到K值得右边，小于K值得数值都转移到其左边
 * 再分别对K值左右两边的一段数组重复以上操作，直至排序完成
 */
public class QuickSort {
    /**
     * 一次排序方法
     * @param a
     * @param start 初始下标
     * @param end 结束下标
     * @return 返回k值下标
     */
    public static int sort(int[] a,int start,int end){
        if(start >= end){
            return -1;
        }

        int s = start;
        int e = end;
        int k = a[s];

        //当初始下标与结尾下标相遇时，停止循环
        while(s < e){
            //左边遍历时，职小于K值时，继续遍历
            while(a[s] < k){
                s ++;
            }
            //右边遍历时，值大于K值时，继续遍历
            while(a[e] > k){
                e --;
            }

            //将左边大于K值得数值，与右边小于K值得数值位置对换。以保证呀小于K值得数都在是、左边，大于K值得数都在右边
            int t = a[s];
            a[s] = a[e];
            a[e] = t;
        }
        return s;
    }

    /**
     * 递归调用aa()方法，当start == end时结束调用
     * @param a
     * @param start
     * @param end
     */
    public static void quickSort(int[] a,int start,int end){
        if(start < end){
            int n = QuickSort.sort(a,start,end);
            quickSort(a,start,n-1);
            quickSort(a,n + 1,end);
        }

    }
    public static void main(String[] args){
        int[] arr = {10,3,5,4,6,2,8,1,11,0};
        quickSort(arr,0,arr.length - 1);
        for(int i = 0;i < arr.length; i ++){
            System.out.println(arr[i]);
        }
    }
}
